class Solution {
public:
	vector<vector<int>> dirs = { {-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2} };

	double knightProbability(int n, int k, int row, int column) {
		//dp存储第k步row,column坐标在棋盘上的位置的概率
		vector<vector<vector<double>>> dp(k + 1, vector<vector<double>>(n, vector<double>(n)));
		for (int step = 0; step <= k; step++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (step == 0) {
						dp[step][i][j] = 1;
					}
					else {
						for (auto& dir : dirs) {
							int ni = i + dir[0], nj = j + dir[1];
							if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
								dp[step][i][j] += dp[step - 1][ni][nj] / 8;//下一步坐标在棋盘上的概率=上一步在棋盘上的概率/8
							}
						}
					}
				}
			}
		}
		return dp[k][row][column];
	}
};